//! ## 27. 移除元素 (easy, array, 双指针)
//! 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
//!
//! 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//!
//! 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

//!
//!
//! #### Example 1
//! ```txt
//! 输入：nums = [3,2,2,3], val = 3
//! 输出：2, nums = [2,2]
//! 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
//! ```
//! #### Example 2
//! ```txt
//! 输入：nums = [0,1,2,2,3,0,4,2], val = 2
//! 输出：5, nums = [0,1,4,0,3]
//! 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
//! ```
//! #### Constraints
//! - `0 <= nums.length <= 100`
//! - `0 <= nums[i] <= 50`
//! - `0 <= val <= 100`
//!
//! ### 知识点
//! - 双指针问题

pub struct Solution;

impl Solution {
    /// #### 思路
    /// 使用双指针, last, cur;
    /// #### 算法
    /// ```txt
    /// last = 0; cur = 0;
    /// *cur 与 val 比较, 相等时跳过
    /// 如果不相等, *last = *cur; cur++; last++;
    /// 新的数组长度就是 last
    /// 将多余的 pop 掉
    /// 返回 last
    /// ```
    /// #### 边界分析
    /// 如果数组为空, 直接返回 0;
    /// #### 复杂度
    /// - 时间复杂度 O(n)
    ///     - 只遍历一遍数组
    /// - 空间复杂度 O(1)
    pub fn solve(arr: &mut Vec<i32>, val: i32) -> usize {
        if arr.is_empty() {
            return 0;
        }
        let mut last = 0;
        for cur in 0..arr.len() {
            if arr[cur] != val {
                arr[last] = arr[cur];
                last += 1;
            }
        }
        while arr.len() > last {
            arr.pop();
        }
        last
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        let mut nums = vec![3, 2, 2, 3];
        let val = 3;
        assert_eq!(Solution::solve(&mut nums, val), 2);
        assert_eq!(nums, vec![2, 2]);
        let mut nums = vec![0, 1, 2, 2, 3, 0, 4, 2];
        let val = 2;
        assert_eq!(Solution::solve(&mut nums, val), 5);
        assert_eq!(nums, vec![0, 1, 3, 0, 4]);
    }
}
